#include "wordprocess.h"

#include <errno.h>
#include <sstream>
#include <fstream>
#include <pthread.h>
#include <errno.h>
#include <vector>
#include <string.h>
#include <math.h>
#include <ext/hash_map>

#include <ext/hash_set>
#include <fstream>

#include "gbk.h"
#include "slog.h"
#include "Config.h"

using namespace std;
using namespace d_utils;
using __gnu_cxx::hash_map;
using __gnu_cxx::hash_set;

#define i2w_max_len 7

struct SimItem
{
	int item;
	float sim;
};

typedef hash_map< int, vector<SimItem> > SimTableType;
typedef SimTableType::iterator SimTableIteratorType;
typedef hash_map< int, hash_map<int, float> > WordSimTableType;
typedef WordSimTableType::iterator WordSimTableIteratorType;

static int word_count = 0, item_count= 0;
static hash_set<string, wp_string_hash> word_set;
static pthread_mutex_t g_lock = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t g_lock1 = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t g_lock2 = PTHREAD_MUTEX_INITIALIZER;
static hash_map<int, pthread_mutex_t> lock_map;
static ofstream sim_out;
static SimTableType similarity, new_sim;
static WordSimTableType word_sim;
static int thread_count = 8, sim_count = 30, wsim_count = 100; 
static long int w2i_max = 0, i2w_max;
static float sim_thres = 1e-5, word_sim_thres = 0, max_word_score;

bool operator < ( const SimItem& left, const SimItem& right )
{
	return left.sim > right.sim;
}


void LoadWords(const char* filename)
{
	ifstream fin(filename);
	if(fin == NULL) 
	{
		Info("cannot read %s", filename);
		return;
	}
	string line;
	vector<int> new_vec;
	Info("loading %s", filename);
	while(getline(fin,line)!=NULL)
	{
		size_t found = line.find(',');
		if(found != string::npos) line.assign(line.substr(0, found));
		else continue;
		word_count++;
		word_set.insert(line);
		id_word[word_count] = line;
		word_id[line] = word_count;
		w2i[word_count]=new_vec;
	}
	fin.close();
	Info("end loading %d %d", word_count, id_word.size());
}

static void ReadItem(const char* itemfile, const int id, const int threads, const int wordlen)
{
	ifstream fin(itemfile);
	if(fin == NULL) Info("cannot read %s", itemfile);

	int count = 0;
	int ret;
	int itemid, last_itemid = 0;
	int owner_id;
	char media_type[10];
	char yy[10];
	char mm[10];
	char dd[10];
	char pub_time[40];
	int channel_id;
	int total_time;	
	char md5[33];
	string line;
	vector<int> new_vector;
	if(id == 0) Info("loading %s", itemfile);
	while(getline(fin,line)!=NULL)
	{
		count++;
		if(count%threads != id) continue;

		const char* txt;

		ret = sscanf(line.c_str(),"\"%d\",\"%d\",\"%10[a-zA-Z]\",\"%10[0-9]-%10[0-9]-%10[0-9] %40[0-9,:]\",\"%d\",\"%d\",\"%32[0-9a-zA-Z]\"",
				&itemid, &owner_id, media_type, yy, mm, dd, pub_time,&channel_id,&total_time,md5);
		if( ret == 10) 
		{
			pthread_mutex_lock(&g_lock);
			item_count++;
			i2w[itemid] = new_vector;
			pthread_mutex_unlock(&g_lock);
			last_itemid = itemid;
		}
		else itemid = last_itemid;

		//get "title","tags","introduction"
		size_t found = 0;
		for(int i=0; i<7; i++)
		{
			found = line.find(",", ++found);
		}
		if(found == string::npos) txt = line.c_str();
		else txt = line.substr(found, line.size()).c_str();

		//strip ", we have title,tag1,tag2...tagn,introduction
		line.assign(txt);
		EraseChar(line, '\"');

		//split by ,
		str_bucket_t buffer, str_chn;
		SplitByChar(buffer, line, ',');

		//process each string, and identify if the string contains Chinese character
		while(!buffer.empty())
		{
			//identify Chinese characters
			line = *(buffer.begin());
			int count = 0;
			bool is_chn = false;
			size_t scan = 0;
			string word;
			while(scan < line.size())
			{
				count ++;
				word = GetGBKChar(line, scan);
				if( isGBK(word))
				{
					if(!is_chn ) is_chn = true;
				}
				scan += word.size();
			}
			if(is_chn)	
			{
				str_chn.push_back(line);
			}
			//else str_eng.push_back(line);
			buffer.erase(buffer.begin());
		}

		hash_map<int, int> wc;
		for(str_bucket_t::iterator str=str_chn.begin(); str!=str_chn.end(); str++)
		{
			size_t scan = 0;
			while(scan < (*str).size())
			{
				bool foundword = false;
				string first = GetGBKChar(*str, scan);
				if( !isGBK(first) ){
					scan += first.size();
					continue;
				}
				for(int i=wordlen; i>=2; i--)
				{
					string word = GetGBKString(*str, scan, i);
					if( 0 == word.compare("") || 4 > word.size()) break;
					if(word_set.find(word) != word_set.end())
					{
						wc[word_id[word]]+=1;
						scan += word.size();
						foundword = true;
						break;
					}
				}
				if(!foundword) scan += first.size();
			}
		}//end for
		vector<SimItem> i2w_local;
		for(hash_map<int, int>::iterator it = wc.begin(); it != wc.end(); it++)
		{
			SimItem si = {it->first, it->second};
			i2w_local.push_back(si);
		}
		sort(i2w_local.begin(), i2w_local.end());
		//if(i2w_local.size() > 10) i2w_local.resize(10);
		for(int i=0; i<i2w_local.size(); i++)
		{
			pthread_mutex_lock(&g_lock);
			i2w[itemid].push_back(i2w_local[i].item);
			w2i[i2w_local[i].item].push_back(itemid);
			pthread_mutex_unlock(&g_lock);
		}
		str_chn.clear();
	}//end read line
	fin.close();
	if(id == 0) Info("end loading %d", i2w.size());
}

struct ReadItemPara
{
	int id, threads, wordlen;
	const char *itemfile;
};

void* LoadItemProc(void* para)
{
	ReadItem(((ReadItemPara*)para)->itemfile, 
			((ReadItemPara*)para)->id, ((ReadItemPara*)para)->threads,
			((ReadItemPara*)para)->wordlen);
	return NULL;
}

void LoadItems(const char* itemfile, int threadcount, int wordlen)
{
	Info("in file %s", itemfile);

	pthread_t threads[threadcount];
	ReadItemPara para[threadcount];

	Info("use %d threads to read item", threadcount);
	for ( int i=0; i<threadcount; i++ )
	{
		para[i].id = i;
		para[i].threads = threadcount;
		para[i].itemfile = itemfile;
		para[i].wordlen = wordlen;
		int ret = pthread_create(&threads[i], NULL, LoadItemProc, &para[i]);
		if ( ret )
		{
			Error("pthread_create return %d, errno is %d", ret, errno);
		}
	}

	for ( int i=0; i<threadcount; i++ )
	{
		pthread_join(threads[i], NULL );
	}

	for(int i=0; i<w2i.size(); i++)
	{
		if(w2i[i].size() > w2i_max)
		{
			pthread_mutex_lock(&g_lock1);
			w2i_max = w2i[i].size();
			pthread_mutex_unlock(&g_lock1);
		}
	}
	for(int i=0; i<i2w.size(); i++)
	{
		if(i2w[i].size() > i2w_max)
		{
			pthread_mutex_lock(&g_lock2);
			i2w_max = i2w[i].size();
			pthread_mutex_unlock(&g_lock2);
		}
	}
	word_sim_thres = 0.9/float(w2i_max);

	Info("finish read item, i2w max %d, w2i max %d, word sim threshold %lf",
			i2w_max, w2i_max, word_sim_thres); 
}

void EmitItemWord(const char* outfile)
{
	ofstream fout(outfile);
	vector<int> map;
	map.resize(1000);
	if(fout == NULL) 
	{
		Info("cannot write %s", outfile);
		return;
	}
	for(hash_map<int, vector<int> >::iterator it = i2w.begin(); it!= i2w.end(); it++)
	{
		map[(it->second).size()]++;
		fout<<(it->first);
		vector<int> &bucket = it->second;
		for(int i=0; i<bucket.size(); i++)
		{
			fout<<','<<id_word[bucket[i]];
		}
		fout<<endl;
	}
	fout.close();

	/*
	stringstream ss;
	for(vector<int>::iterator it = map.begin(); it != map.end(); it++)
	{
		ss<<(*it)<<'\t';
	}
	Debug(ss.str().c_str());
	*/
}

int LoadSimtable(const char * filename)
{
	const char * p;
	struct timeval tv;
	int itemId, n;

	string line;
	int count = 0, badline=0;
	if( access( filename, 0 ) )
		return 1;
	ifstream fin(filename);
	float f;
	SimTableType sim;
	Info("load... data from %s", filename);
	while( getline(fin, line) != NULL )
	{
		count++;
		p = line.c_str();
		itemId = atoi(p);
		if (itemId <= 0 )
		{
			badline++;
			continue;
		}

		vector<SimItem> v;
		while((p=strchr(p, '\t')) != NULL)
		{
			n = atoi(++p);
			if ( (p = strchr(p, ':')) == NULL )
				break;

			f = (float)atof(++p);
			SimItem si = {n, f};
			v.push_back(si);
		}
		sim[itemId] = v;
	}
	fin.close();
	SimTableIteratorType tg_line;
	for ( SimTableType::iterator it_line = sim.begin(); it_line != sim.end(); ++it_line )
	{
		for ( vector<SimItem>::iterator it_row = (it_line->second).begin(); it_row != (it_line->second).end(); ++it_row )
		{
			if(it_row->item <= it_line->first)
			{
				continue;
			}
			tg_line = sim.find(it_row->item);
			if (tg_line != sim.end())
			{
				vector<SimItem> &tg_row = tg_line->second;
				n = it_line->first; 
				f = it_row->sim;
				SimItem si = {n, f};
				tg_row.push_back(si);
			}

		}
	}

	for ( SimTableType::iterator it_line = sim.begin(); it_line != sim.end(); ++it_line )
	{
		sort((it_line->second).begin(),(it_line->second).end());
	}

	similarity.clear();
	for ( SimTableType::const_iterator it=sim.begin(); it != sim.end(); ++it )
	{
		vector<SimItem> v(it->second);
		similarity[it->first] = v;
	}
	sim.clear();

	Info( "reload_data, total line is %d, sim.size=%zd"
			, count, similarity.size());

	return 0;
}

void Calcfscore(const int id, const int threads)
{
	int count=0;
	for(SimTableIteratorType it = similarity.begin(); it!= similarity.end(); it++)
	{
		count++;
		if(count % threads != id) continue;
		//if(count % 100000 < threads-1 && id == 0) Info("%d", count);
		if(i2w.find(it->first) == i2w.end()) continue;
		vector<int> &word1vec = i2w[it->first];
		vector<SimItem> &recvec = it->second;
		for(int i=0; i<recvec.size(); i++)
		{
			hash_set<int> word2set;
			if(i2w.find(recvec[i].item) == i2w.end()) continue;
			vector<int> &word2vec = i2w[recvec[i].item];
			for(int j=0; j<word1vec.size(); j++)
			{
				int word1 = word1vec[j];
				if(lock_map.find(word1) == lock_map.end() ||
						word_sim.find(word1) == word_sim.end())
				{
					Error("map error");
					continue;
				}
				hash_map<int, float> &scoremap = word_sim[word1];
				pthread_mutex_t *ilock = &lock_map[word1];
				float score = recvec[i].sim / float(word2vec.size() + w2i_max);
				if(score <= word_sim_thres) continue;
				for(int k=0; k<word2vec.size(); k++)
				{
					int word2 = word2vec[k];
					pthread_mutex_lock(ilock);
					scoremap[word2] += score;
					if(max_word_score < scoremap[word2]) max_word_score = scoremap[word2];
					pthread_mutex_unlock(ilock);
				}
			}//done word1vec
		}//done recvec
	}//done simtable
}

struct CalcfscoreParam
{
	int id, threads;
};

void *CalcfscoreProc(void *param)
{
	Calcfscore(
		((CalcfscoreParam *)param)->id, 
		((CalcfscoreParam *)param)->threads
		);
	return NULL;
}

void CalWordSim(const int threadcount, const int wsimcount)
{
	wsim_count = wsimcount;
	pthread_t threads[threadcount];
	CalcfscoreParam para[threadcount];
	hash_map<int, float> sim_item_map;
	pthread_mutex_t new_lock = PTHREAD_MUTEX_INITIALIZER;
	for(hash_map<int, vector<int> >::iterator it = w2i.begin(); it != w2i.end(); it++)
	{
		word_sim[it->first] = sim_item_map;
		lock_map[it->first] = new_lock;
	}

	Info("use %d threads to cal word sim", threadcount);
	for ( int i=0; i<threadcount; i++ )
	{
		para[i].id = i;
		para[i].threads = threadcount;
		int ret = pthread_create(&threads[i], NULL, CalcfscoreProc, &para[i]);
		if ( ret )
		{
			Error("pthread_create return %d, errno is %d", ret, errno);
		}
	}

	for ( int i=0; i<threadcount; i++ )
	{
		pthread_join(threads[i], NULL );
	}

	Info("finish cal word sim %d, max word score %f", word_sim.size(), max_word_score); 

	int sum_len = 0, sum_line = 0;

	//normalize scores
	for(WordSimTableIteratorType it = word_sim.begin(); it!= word_sim.end(); it++)
	{
		hash_map<int, float> &bucket = it->second;
		if(bucket.size() == 0)
		{
			continue;
		}
		else
		{
			sum_line++;
		}
		float max = 0;
		for(hash_map<int, float>::iterator it = bucket.begin(); it != bucket.end(); it++)
		{
			it->second = (it->second)/max_word_score;
		}
		sum_len+=bucket.size();
	}
	Info("finish sort item, sim size %d, averglen %f", sum_line, sum_len/float(sum_line)); 
}

void Emitcfscore(const char* outfile)
{
	ofstream fout(outfile);
	if(fout == NULL) 
	{
		Info("cannot write %s", outfile);
		return;
	}

	SimTableType wsim;
	for(WordSimTableIteratorType it = word_sim.begin(); it != word_sim.end(); it++)
	{
		int word = it->first;
		hash_map<int, float> &map = it->second;
		for(hash_map<int, float>::iterator itt = map.begin(); itt != map.end(); itt++)
		{
			SimItem si = {itt->first, itt->second};
			wsim[word].push_back(si);
		}
		sort(wsim[word].begin(), wsim[word].end());
	}

	for(SimTableIteratorType it = wsim.begin(); it!= wsim.end(); it++)
	{
		vector<SimItem> &recvec = it->second;
		if( recvec.size() == 0) continue;
		fout<<id_word[it->first]<<':';
		for(int i=0; i<recvec.size(); i++)
		{
			fout<<'\t'<<id_word[recvec[i].item]<<','<<recvec[i].sim;
		}
		fout<<endl;
	}
	fout.close();
}

static float simij(const int i, const int j)
{
	float ret = 0;
	hash_map<int, vector<int> >::iterator iiter = i2w.find(i);
	hash_map<int, vector<int> >::iterator jiter = i2w.find(j);
	if( iiter == i2w.end() || jiter == i2w.end()) return ret;
	vector<int> &iword = i2w[i];
	vector<int> &jword = i2w[j];
	for(int m=0; m<iword.size(); m++)
	{
		int word1 = iword[m];
		WordSimTableIteratorType it = word_sim.find(word1);
		if (it != word_sim.end())
		{
			hash_map<int, float> &sim_map = it->second;
			for(int n=0; n<jword.size(); n++)
			{
				hash_map<int, float>::iterator itt = sim_map.find(jword[n]);
				if(itt != sim_map.end()) ret += (itt->second);
			}
		}
	}
	return ret/float(i2w[j].size());
}

static void printij(const int i, const int j)
{
	hash_map<int, vector<int> >::iterator iiter = i2w.find(i);
	hash_map<int, vector<int> >::iterator jiter = i2w.find(j);
	if( iiter == i2w.end() || jiter == i2w.end()) return;
	vector<int> &iword = i2w[i];
	vector<int> &jword = i2w[j];
	for(int m=0; m<iword.size(); m++)
	{
		int word1 = iword[m];
		WordSimTableIteratorType it = word_sim.find(word1);
		if (it != word_sim.end())
		{
			hash_map<int, float> &sim_map = it->second;
			for(int n=0; n<jword.size(); n++)
			{
				int word2 = jword[n];
				hash_map<int, float>::iterator itt = sim_map.find(word2);
				if(itt != sim_map.end()) 
				{
					Debug("%d %d | %s %s | %f", i, j, id_word[word1].c_str(),
							id_word[word2].c_str(), itt->second);
				}
			}
		}
	}
	return ;
}

static void cal_sim_oneline(const int item1)
{
	hash_set<int> calitem;
	vector<SimItem> sim_vec;
	if(i2w.find(item1) == i2w.end()) return;
	vector<int> &word_buck = i2w[item1];
	for(int i=0; i<word_buck.size(); i++)
	{
		int word1 = word_buck[i];
		if(word_sim.find(word1) == word_sim.end()) continue;
		hash_map<int, float> &word_score = word_sim[word1];
		for(hash_map<int, float>::iterator it = word_score.begin(); it != word_score.end(); it++)
		{
			int word2 = it->first;
			if(w2i.find(word2) == w2i.end()) continue;
			vector<int> &item_vec = w2i[word2];
			for(int k=0; k<item_vec.size(); k++)
			{
				int item2 = item_vec[k];
				if(calitem.find(item2) != calitem.end()) continue;
				float sim = simij(item1, item2);
				if(sim >= sim_thres) 
				{
					Debug("%f", sim);
					printij(item1, item2);
					SimItem si = {item2, sim};
					sim_vec.push_back(si);
				}
				calitem.insert(item2);
			}
		}
	}
		
	if(sim_vec.empty()) return;
	sort(sim_vec.begin(), sim_vec.end());
	if(sim_vec.size() > sim_count) sim_vec.resize(sim_count);
				
	stringstream ss;
	ss<<item1;
	for(int i=0; i<sim_vec.size(); i++)
	{
		ss<<'\t'<<sim_vec[i].item<<':'<<sim_vec[i].sim;
	}
	ss<<endl;
	pthread_mutex_lock(&g_lock);
	sim_out<<ss.str().c_str();
	ss.clear();
	pthread_mutex_unlock(&g_lock);
}

static void CalSimLocal(const int id)
{
	int count = 0;
	float pct = 0;
	for(hash_map<int, vector<int> >::iterator it = i2w.begin(); it != i2w.end(); it++)
	{
		count++;
		if( count / float(i2w.size()) >= pct)
		{
			Info("thread %d finish %d", id, int(pct*100));
			pct += 0.01;
		}
		if( count % thread_count != id) continue;
		cal_sim_oneline(it->first);
	}
	Info("thread %d ends", id);
}

/*
static void cal_sim_oneword(const int word1)
{
	if(word_sim.find(word1) == word_sim.end()) return;
	vector<SimItem> score_vec = word_sim[word1];
	for(int i=0; i<score_vec.size(); i++)
	{
		int word2 = score_vec[i].item;
		float score = score_vec[i].sim;
		if(w2i.find(word1) == w2i.end() || w2i.find(word2) == w2i.end()) return;
		hash_set<int> item2_set;
		vector<int> &item_bucket1 = w2i[word1];
		vector<int> &item_bucket2 = w2i[word2];
		for(int j=0; j<item_bucket2.size(); j++) item2_set.insert(item_bucket2[j]);
		for(int j=0; j<item_bucket1.size(); j++)
		{
			int item1 = item_bucket1[j];
			if(new_sim.find(item1) == new_sim.end()) return;
			vector<SimItem> &sim_vec = new_sim[item1];
			if(lock_map.find(item1) == lock_map.end()) return;
			pthread_mutex_t &lock = lock_map[item1];
			for(int k=0; k<sim_vec.size(); k++)
			{
				int sim_word = sim_vec[k].item;
				hash_set<int>::iterator it = item2_set.find(sim_word);
				if(it != item2_set.end())
				{
					pthread_mutex_lock(&lock);
					sim_vec[k].sim += score;
					pthread_mutex_unlock(&lock);
				}
			}
			while(!item2_set.empty())
			{
				SimItem si = {*item2_set.begin(), score};
				pthread_mutex_lock(&lock);
				sim_vec.push_back(si);
				pthread_mutex_unlock(&lock);
				item2_set.erase(item2_set.begin());
			}
		}//end item_bucket1
	}//end score_vec
}
*/

/*
static void CalSimLocal(const int id)
{
	int count = 0;
	float pct = 0;
	for(SimTableIteratorType it = word_sim.begin(); it != word_sim.end(); it++)
	{
		count++;
		if( count / float(word_sim.size()) >= pct)
		{
			Info("thread %d finish %d", id, int(pct*100));
			pct += 0.01;
		}
		if( count % thread_count != id) continue;
		cal_sim_oneword(it->first);
	}
	Info("thread %d ends", id);
}
*/

void* CalSimProc(void * para)
{
	CalSimLocal(*(int*)para);
	return NULL;
}

void CalSim(const int threadcount, const float simthres, const int simcount, const char* outfile)
{
	sim_out.open(outfile);
	if( !sim_out.is_open())
	{
		Error("%s cannot be opened", outfile);
		return;
	}

	thread_count = threadcount;
	sim_thres = simthres;
	sim_count = simcount;
	pthread_t threads[thread_count];
	int para[thread_count];
	vector<SimItem> new_vec;
	pthread_mutex_t new_lock = PTHREAD_MUTEX_INITIALIZER;
	lock_map.clear();
	/*
	for(hash_map<int, vector<int> >::iterator it = i2w.begin(); it != i2w.end(); it++)
	{
		lock_map[it->first] = new_lock;
		new_sim[it->first] = new_vec;
	}
	*/

	Info("use %d threads to cal sim", thread_count);
	for ( int i=0; i<thread_count; i++ )
	{
		para[i] = i;
		int ret = pthread_create(&threads[i], NULL, CalSimProc, &para[i]);
		if ( ret )
		{
			Error("pthread_create return %d, errno is %d", ret, errno);
		}
	}

	for ( int i=0; i<threadcount; i++ )
	{
		pthread_join(threads[i], NULL );
	}

	Info("finish cal sim"); 
	sim_out.close();
}

void EmitNewSim(const char* outfile)
{
	ofstream fout(outfile);
	if(fout == NULL) 
	{
		Info("cannot write %s", outfile);
		return;
	}
	for(SimTableIteratorType it = new_sim.begin(); it!= new_sim.end(); it++)
	{
		vector<SimItem> &recvec = it->second;
		if( recvec.size() == 0) continue;
		fout<<id_word[it->first];
		for(int i=0; i<recvec.size(); i++)
		{
			fout<<'\t'<<id_word[recvec[i].item]<<':'<<recvec[i].sim;
		}
		fout<<endl;
	}
	fout.close();
}

void Clustering(const char * cfile, const float pct, const int size_thres, const int top_word)
{
	ofstream fout(cfile);
	if(fout == NULL) 
	{
		Info("cannot write %s", cfile);
		return;
	}
	vector<SimItem> itemvec;
	hash_set<int> itemset;
	for(SimTableIteratorType it = similarity.begin(); it != similarity.end(); it++)
	{
		SimItem si = {it->first, (it->second)[0].sim};
		itemvec.push_back(si);
		itemset.insert(it->first);
	}
	sort(itemvec.begin(), itemvec.end());
	while(!itemset.empty())
	{
		clustercount++;
		int item1 = itemvec[0].item;
		itemvec.erase(itemvec.begin());
		itemset.erase(item1);
		SimTableIteratorType it = similarity.find(item1);
		if(it == similarity.end()) continue;
		vector<SimItem> &bucket = it->second;
		float max_score = bucket[0].sim*pct;
		hash_set<int> neighbor, cluster;
		cluster.insert(item1);
		//push neighbor of item1
		for(int i=0; i<bucket.size(); i++)
		{
			int item2 = bucket[i].item;
			if( 
					itemset.find(item2) != itemset.end()
					&& bucket[i].sim >= max_score
			  )
			{
				neighbor.insert(item2);
				cluster.insert(item2);
				itemset.erase(item2);
				for(int j=0; j<itemvec.size(); j++)
				{
					if(itemvec[j].item == item2)
					{
						itemvec.erase(itemvec.begin()+j);
						break;
					}
				}
			}
		}

		//push neighbor of neighbors
		while(!neighbor.empty())
		{
			int item2 = *(neighbor.begin());
			neighbor.erase(neighbor.begin());
			SimTableIteratorType itt = similarity.find(item2);
			if(itt == similarity.end()) continue;
			vector<SimItem> &bucket2 = itt->second;
			for(int i=0; i<bucket2.size(); i++)
			{
				int item3 = bucket2[i].item;
				//push neighbor of item2
				if( 
						itemset.find(item3) != itemset.end()
						&& bucket2[i].sim >= max_score
				  )
				{
					neighbor.insert(item3);
					cluster.insert(item3);
					itemset.erase(item3);
					for(int j=0; j<itemvec.size(); j++)
					{
						if(itemvec[j].item == item2)
						{
							itemvec.erase(itemvec.begin()+j);
							break;
						}
					}
				}//end item3
			}//end bucket2
		}//end push neighbor of neighbors
		if(cluster.size() < size_thres) continue;
		int clustercount = 0;

		//count word occurence of a cluster
		hash_map<int, int> word_count;
		for(hash_set<int>::iterator iter = cluster.begin(); iter != cluster.end(); iter++)
		{
			int word = *iter;
			if(i2w.find(word) != i2w.end())
			{
				vector<int> &bucket = i2w[word];
				for(int i=0; i<bucket.size(); i++)
				{
					word_count[bucket[i]] += 1;
				}
			}
		}
		vector<SimItem> word_vec;
		for(hash_map<int, int>::iterator iter = word_count.begin(); iter!= word_count.end(); iter++)
		{
			SimItem si = {iter->first, iter->second};
		}
		sort(word_vec.begin(), word_vec.end());
		word_vec.resize(top_word);

		//output
		stringstream ss;
		ss<<"cluster"<<clustercount<<"size"<<cluster.size()<<endl;
		for(hash_set<int>::iterator iter = cluster.begin(); iter != cluster.end(); iter++)
		{
			ss<<*iter<<',';
		}
		ss<<endl;
		for(int i=0; i<word_vec.size(); i++)
		{
			ss<<id_word[word_vec[i].item]<<','<<word_vec[i].sim<<'\t';
		}
		ss<<endl;
		fout<<ss.str().c_str();
		Debug("%d", itemset.size());
	}//end all items
	fout.close();
}

			
